package everydayone.movingCount;
/**
 * @Date 2020/04/08
 * @author 王光浩
 * @Thinking 使用深度优先搜索（递归）
 */
public class MyMethodTwo {
	public int movingCount(int m, int n, int k) {
		boolean[][] flag=new boolean[m][n];
		return helper(0,0,flag,k);
	}
	private int helper(int x,int y,boolean[][] flag,int k) {
		if(x>=flag.length || y>=flag[0].length || flag[x][y])return 0;
		flag[x][y]=true;
		int sum=0;
		int xx=x;
		int yy=y;
		while(xx>0) {
			sum+=xx%10;
			xx/=10;
		}
		while(yy>0) {
			sum+=yy%10;
			yy/=10;
		}
		if(sum>k)return 0;
		return 1+helper(x+1,y,flag,k)+helper(x,y+1,flag,k);
	}
}
